In a storage device which includes a nonvolatile semiconductor memory such as a flash memory and is known as a solid state drive (SSD) having the same interface as a hard disk drive (HDD), a unit of data erasure is different from a unit of data read/write. As an example, the unit of data erasure is a physical block and the unit of data read/write is a cluster, which is smaller than the unit of data erasure, because one physical block includes many word lines, one word line many pages, and one page a plurality of clusters.
In the SSD, if data rewriting is performed, there is a high possibility that a valid cluster and an invalid cluster will coexist in the physical block. The valid cluster is a cluster whose physical address is designated by a logical address/physical address conversion table, and the invalid cluster is a cluster whose physical address is not designated by the logical address/physical address conversion table. If the size of the physical block increases, a storage area cannot be utilized effectively.
In order to effectively utilize the storage area, processing called compaction or garbage collection (hereinafter, referred to as garbage collection or GC) is performed. In the garbage collection, in order to increase the number of free blocks in which data is erased, data of all valid clusters in a logical block (referred to as a GC original logical block) including a physical block in which valid and invalid clusters coexist is moved to an erased logical block (referred to as a GC destination logical block). All the data of the GC original logical block from which the data of all the valid clusters is moved to the GC destination logical block are erased. The erased GC original logical block is released as a free block and can be reused as the GC destination logical block.
When reading the data of the cluster in the GC original logical block, an error may occur in the read data, and the error may be uncorrectable in some cases. In this case, whether the cluster from which the data is read is a valid cluster or an invalid cluster cannot be determined. Accordingly, if a read error occurs in data of a certain cluster and the error cannot be corrected, the garbage collection cannot be performed, the data of the GC original logical block cannot be erased, and the GC original logical block cannot be reused as the GC destination logical block.
In such a storage device, when reading data of a cluster of a GC original logical block, if a read error occurs and the error cannot be corrected, there is a concern that a GC destination logical block is exhausted and the garbage collection cannot be performed.